1. Field of the Invention
This invention relates to a method and apparatus for dividing decimal numbers, and more particularly, to an efficient method and apparatus for dividing decimal numbers using a computer which lacks an instruction for either division or multiplication.
2. Description of Related Art
In the past, a simple method for performing long division by a programmed computer subtracted a divisor from a dividend until the result of the subtraction operation was a negative value. The number of subtractions minus 1 yields the quotient. The remainder of the division was determined by adding the divisor to the negative result.
Alternatively, the divisor is repeatedly subtracted from a portion of the dividend comprising a like number of leading digits of the dividend. If the first subtraction is negative, the division is subtracted from a like number of leading dividend digits plus 1. Otherwise, once the result of the subtraction is negative, no further subtractions are performed and the divisor is added to the negative result to attain the remainder. The number of subtractions minus 1 comprises a first digit of the quotient. The process is repeated with the divisor being subtracted from the remainder, and modified by appending additional digits from the original dividend to equal the number of divisor digits. The number of such subtractions minus 1 is appended as a next digit of the quotient.
This improved method for determining the quotient of a division operation is still time consuming due to the large number of subtraction operations that must be performed when dividing a large dividend by a relatively small divisor.
A number of methods have been devised to reduce the number of subtraction or addition operations needed to calculate the quotient (subtraction operations are the equivalent of addition operations for most purposes, and in particular for digital computers). One such method, disclosed in U.S. Pat. No. 3,736,413 issued to the present inventor, is similar to the common manual long division method, in that a trial quotient digit is selected based upon the value of the first digits of the dividend and the divisor. In order to limit the number of potential trial quotient digits, the divisor is normalized to fall within a predetermined range. In the case of a decimal division operation, the divisor is normalized to be greater than or equal to 0.5 and less than 1, and such that the first three digits from left to right of the divisor are greater than 625. The latter normalization characteristic is achieved by multiplying the divisor and the dividend by a common factor, preferably a power of two, until the desired value is obtained. Powers of two are selected to allow the divisor and dividend to each be added to themselves to effect the multiplication operation in a reduced number of addition operations. Normalizing the divisor and the dividend ensures that the trial quotient digit will be within two digits of the actual quotient digit.
Once the divisor is normalized, a trial quotient digit is selected based upon the values of the leading digit of the divisor and the leading digit of the dividend.
However, since the trial quotient digit is only guaranteed to be within two digits of the actual quotient digit, there are times when two tests must be performed to determine which one of three possible quotient digits is the actual quotient digit. Each of these tests includes a subtraction operation.
Because increased speed and efficiency are desirable in computers, it is desirable to reduce the number of steps in the long division process by identifying actual quotient digits more efficiently. The present invention is a method and apparatus which determines actual quotient digits with a single addition or subtraction operation, thus resulting in more efficient computerized long division operation.